package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/description
 *
 * 题型： 二叉树的前序遍历 + 哈希法
 *
 * ```
 * 653. 两数之和 IV - 输入二叉搜索树
 * 给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 *
 * 示例 1：
 * 输入: root = [5,3,6,2,4,null,7], k = 9
 * 输出: true
 *
 * 示例 2：
 * 输入: root = [5,3,6,2,4,null,7], k = 28
 * 输出: false
 *
 *
 * 提示:
 * 二叉树的节点个数的范围是  [1, 104].
 * -104 <= Node.val <= 104
 * 题目数据保证，输入的 root 是一棵 有效 的二叉搜索树
 * -105 <= k <= 105
 * ```
 */
class leetcode_653 {
    @Test
    fun test_1() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val root = n5

        n5.left = n3
        n5.right = n6

        n3.left = n2
        n3.right = n4

        n6.right = n7
        val actual = findTarget(root, 9)
        val expected = true
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val root = n5

        n5.left = n3
        n5.right = n6

        n3.left = n2
        n3.right = n4

        n6.right = n7
        val actual = findTarget(root, 28)
        val expected = false
        Assert.assertEquals(expected, actual)
    }


    private val set: HashSet<Int> = HashSet()
    private fun findTarget(root: TreeNode?, k: Int): Boolean {
        /**
        题型： 二叉树的前序遍历 + 哈希法
        思路：
        遍历节点p，判断 (k - p value) 是否在set 中，若存在，说明找到了和，则返回true，没有不存在，存放set中，继续遍历。
        这种思路没有利用二叉搜索树的特性。

        https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/solutions/1354976/by-ac_oier-zr4o
         */
        // 1 函数参数以及返回值
        // 2 确定终止条件
        if (null == root) {
            return false
        }
        // println("root=${root.`val`},k=$k")

        // 3 确定单层递归的处理逻辑
        // 中
        if (set.contains(k - root.`val`)) {
            return true
        }
        set.add(root.`val`)

        // 左
        val isLeftFound = findTarget(root.left, k)

        // 右
        val isRightFound = findTarget(root.right, k)

        return isLeftFound || isRightFound
    }
}